class Solution
{
public:
    vector<int> smallestMissingValueSubtree(vector<int> &parents, vector<int> &nums)
    {
        int n = parents.size();
        vector<int> inDegree(n, 0);
        vector<int> answer(n, 0);
        vector<vector<int>> children(n, vector<int>());

        vector<int> ufs(10e5 + 2, -1);
        iota(ufs.begin(), ufs.end(), 0);
        function<int(int)> find = [&](int x)
        {
            if (ufs[x] == x)
            {
                return x;
            }
            return ufs[x] = find(ufs[x]);
        };

        function<void(int, int)> merge = [&](int x, int y)
        {
            int fx = find(x);
            int fy = find(y);
            if (fx != fy)
            {
                ufs[fx] = fy;
            }
        };

        for (int i = 1; i < n; ++i)
        {
            ++inDegree[parents[i]];
            children[parents[i]].push_back(i);
        }
        queue<int> q;

        for (int i = 0; i < n; ++i)
        {
            if (inDegree[i] == 0)
            {
                q.push(i);
            }
        }
        while (!q.empty())
        {
            int node = q.front();
            q.pop();
            if (node != 0)
            {
                int p = parents[node];
                --inDegree[p];
                if (inDegree[p] == 0)
                {
                    q.push(p);
                }
            }
            if (children[node].size() == 0)
            {
                answer[node] = nums[node] == 1 ? 2 : 1;
            }
            else
            {
                int missing = 1;
                for (int child : children[node])
                {
                    missing = max(missing, answer[child]);
                    merge(nums[child], nums[node]);
                }
                while (find(missing) == find(nums[node]))
                {
                    ++missing;
                }
                answer[node] = missing;
            }
        }
        return answer;
    }
};